package simple.tree;

import struct.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/find-mode-in-binary-search-tree/">501. 二叉搜索树中的众数</a>
 * 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
 * 如果树中有不止一个众数，可以按 任意顺序 返回。
 * 假定 BST 满足如下定义：
 *   结点左子树中所含节点的值 小于等于 当前节点的值
 *   结点右子树中所含节点的值 大于等于 当前节点的值
 *   左子树和右子树都是二叉搜索树
 * 示例 1：
 *   输入：root = [1,null,2,2]
 *   输出：[2]
 * 示例 2：
 *   输入：root = [0]
 *   输出：[0]
 * 提示：
 *   树中节点的数目在范围 [1, 10^4] 内
 *   -10^5 <= Node.val <= 10^5
 * @author 刘学松
 * @date 2023-05-17 16:28
 */
public class 二叉搜索树中的众数 {
    List<Integer> list = new ArrayList<>();
    int curr,count,maxCount;
    public int[] findMode(TreeNode root) {
        dfs(root);
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    private void dfs(TreeNode root) {
        if (root != null) {
            dfs(root.left);
            if (root.val == curr) {
                ++count;
            } else {
                count = 1;
                curr = root.val;
            }
            if (count == maxCount) {
                list.add(root.val);
            } else if (count > maxCount) {
                maxCount = count;
                list.clear();
                list.add(root.val);
            }
            dfs(root.right);
        }
    }
}
